﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMeansAlgorithm
{
    public class KMeans
    {
        private int _k, _d;
        private double[][][] _centroidHistory; //double[K][D]
        private List<ClusteredData> _dataSet; //double[D]
        private static readonly double epsilon = 0.000000001;
        
        private double[][] _CurrentCentroids
        {
            get
            {
                return _centroidHistory[0];
            }
            set
            {
                _centroidHistory[0] = value;
            }
        }

        public KMeans(int k, int d)
        {
            this._k = k;
            this._d = d;
            this._dataSet = new List<ClusteredData>();
            this._centroidHistory = new double[2][][];
        }

        public KMeans(int k, int d, double[][] centroids)
            : this(k, d)
        {
            this._centroidHistory[0] = centroids;
        }

        private void shiftCentroidHistory(double[][] newCentroidData)
        {
            this._centroidHistory[1] = this._centroidHistory[0];
            this._centroidHistory[0] = newCentroidData;
        }

        public void AddData(double[] data, string id)
        {
            if (data.Length != _d)
            {
                throw new ArgumentException("Invalid data dimension! It is = " + data.Length
                    + " but should be " + _d);
            }

            _dataSet.Add(new ClusteredData(data, id));
        }

        public void RemoveDataAtIndex(int index)
        {
            if (index < 0 || index >= _dataSet.Count)
            {
                throw new IndexOutOfRangeException(index + 
                    " is not a valid index! Should be between 0 and " + (_dataSet.Count - 1));
            }

            _dataSet.RemoveAt(index);
        }

        public KMeansResult Cluster()
        {
            while (centroidsChanged())
            {
                assignClusters();

                var newCentroids = calculateNewCentroids();

                shiftCentroidHistory(newCentroids);
            }

            return new KMeansResult()
            {
                Centroids = _CurrentCentroids,
                ClusteredDataSet = _dataSet
            };
        }

        public IEnumerable<ClusteredData> GetDatasInCluster(int cluster)
        {
            return from data in _dataSet
                   where data.ClusterNumber == cluster
                   select data;
        }

        public int ClusterOf(double[] data)
        {
            var distances = new List<double>();

            for (int i = 0; i < _k; ++i)
            {
                distances.Add(distance(data, _CurrentCentroids[i]));
            }

            return distances.IndexOf(distances.Min());
        }

        private void assignClusters()
        {
            foreach (var data in _dataSet)
            {
                data.ClusterNumber = ClusterOf(data.Data);
            }
        }

        private double[][] calculateNewCentroids()
        {
            double[][] newCentroids = new double[_k][];
            
            for (int i = 0; i < _k; ++i)
            {
                newCentroids[i] = new double[_d];
                var _datasInCluster = GetDatasInCluster(i);
                
                for (int j = 0; j < _d; ++j)
                {
                    var _innerSum = 0.0;

                    foreach (var dat in _datasInCluster)
                    {
                        _innerSum += dat.Data[j];
                    }

                    newCentroids[i][j] = _innerSum / _datasInCluster.Count();
                }
            }

            return newCentroids;
        }

        private double distance(double[] p1, double[] p2)
        {
            if (p1.Length != p2.Length)
            {
                throw new ArgumentException("Lengths of points p1 and p2 should be same! Where p1 is " + p1.Length + 
                    " and p2 is " + p2.Length + " long");
            }

            var length = p1.Length;
            var innerResult = 0.0;
            var power = 1.0 / length;

            for (int i = 0; i < length; ++i)
            {
                innerResult += (p2[i] - p1[i]) * (p2[i] - p1[i]);
            }

            var result = Math.Pow(innerResult, power);

            return result;
        }

        private bool centroidsChanged()
        {
            if (_centroidHistory[1] == null)
            {
                return true;
            }

            for (int i = 0; i < _k; ++i)
            {
                for (int j = 0; j < _d; ++j)
                {
                    if (Math.Abs(_centroidHistory[0][i][j] - _centroidHistory[1][i][j]) > epsilon)
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    }
}
